package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/10 10:12
 */
public class _927 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(threeEqualParts(new int[]{1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,0})));
    }
    public static int[] threeEqualParts(int[] A) {
        int [] B = new int[A.length];
        int num = 0;
        for(int i=0;i<A.length;i++){
            if(A[i]==1){
                B[num] = i;
                num++;
            }
        }
        int[] daan = new int[]{-1,-1};
        if(num%3==0&&num!=0){
            int a = B[0];
            int b = B[num/3];
            int c = B[num/3*2];

            while(c<A.length&&a<B[num/3]&&b<B[num/3*2]){
                if(A[a]==A[c]&&A[a]==A[b]){
                    a++;
                    b++;
                    c++;
                }else{
                    return daan;
                }
            }
            if(c==A.length){
                daan[0] = a-1;
                daan[1] = b;
            }
        }
        if(num==0){
            daan[0] = 0;
            daan[1] = A.length-1;
        }
        return daan;
    }



    class Solution {
        public int[] threeEqualParts(int[] A) {
            //开幕雷击
            int sumOne = 0;
            for(int i : A) {
                sumOne += i;
            }
            if(sumOne % 3 != 0)
                return new int[]{-1, -1};
            //System.out.println("pass0");
            if(sumOne == 0) {
                return new int[]{0, 2};
            }
            int inEach = sumOne / 3;
            //走流程呗
            int tail0 = 0; //末尾有几个0
            int r = A.length - 1, l = 0;
            while(A[r] == 0) {
                ++tail0;
                --r;
            }
            while(A[l] == 0) {
                ++l;
            }
            int numBeg = l;
            for(int i = 0; i < inEach;) {
                i += A[r];
                --r;
            }
            //r指向右数的第一个前导0
            int rr = r + 1;
            while(rr < A.length) {
                //System.out.println("l = " + l + " rr = " + rr);
                if(A[l] != A[rr])
                    return new int[]{-1, -1};
                ++rr;
                ++l;
            }
            //此时l指向左数的最后一位往右一个格
            //System.out.println("pass l r");
            int ll = l;
            while(A[ll] == 0)
                ++ll;//读去前导0
            while(numBeg < l) {
                if(A[numBeg] != A[ll])
                    return new int[]{-1, -1};
                ++ll;
                ++numBeg;
            }
            return new int[]{l - 1, ll};
        }
    }
}
